|
In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: * It always returns the correct YES or NO answer. * The running time is polynomial in expectation for every input. In other words, if the algorithm is allowed to flip a truly-random coin while it is running, it will always return the correct answer and, for a problem of size ''n'', there is some polynomial ''p''(''n'') such that the average running time will be less than ''p''(''n''), even though it might occasionally be much longer. Such an algorithm is called a Las Vegas algorithm. Alternatively, ZPP can be defined as the class of problems for which a probabilistic Turing machine exists with these properties: * It always runs in polynomial time. * It returns an answer YES, NO or DO NOT KNOW. * The answer is always either DO NOT KNOW or the correct answer. * It returns DO NOT KNOW with probability at most 1/2 (and the correct answer otherwise). The two definitions are equivalent. The definition of ZPP is based on probabilistic Turing machines, but, for clarity, note that other complexity classes based on them include BPP and RP. The class BQP is based on another machine with randomness: the quantum computer. == Intersection definition == The class ZPP is exactly equal to the intersection of the classes RP and co-RP. This is often taken to be the definition of ZPP. To show this, first note that every problem which is in ''both'' RP and co-RP has a Las Vegas algorithm as follows: * Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co-RP algorithm B. * Given an input in L, run A on the input for one step. If it returns YES, the answer must be YES. Otherwise, run B on the input for one step. If it returns NO, the answer must be NO. If neither occurs, repeat this step. Note that only one machine can ever give a wrong answer, and the chance of that machine giving the wrong answer during each repetition is at most 50%. This means that the chance of reaching the ''k''th round shrinks exponentially in ''k'', showing that the expected running time is polynomial. This shows that RP intersect co-RP is contained in ZPP. To show that ZPP is contained in RP intersect co-RP, suppose we have a Las Vegas algorithm C to solve a problem. We can then construct the following RP algorithm: * Run C for at least ''double'' its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO. By Markov's Inequality, the chance that it will yield an answer before we stop it is 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is only 1/2, fitting the definition of an RP algorithm. The co-RP algorithm is identical, except that it gives YES if C "times out". 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ZPP (complexity)」の詳細全文を読む スポンサード リンク
|